package com.theeviljames.dijkstra;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Enumeration;
import java.util.Hashtable;
import java.util.PriorityQueue;
import java.util.Random;

import com.theeviljames.graph.Graph;

public class Dijkstra {

	private Graph graph;
	private static final String start = "s";
	public static final Random rand = new Random();
	private ArrayList<PVertex> cloud;
	private PriorityQueue<PVertex> queue;
	
	public Dijkstra(Graph g) {
		graph = g;
		cloud = new ArrayList<PVertex>();
		queue = new PriorityQueue<PVertex>();
	}
	
	public void init(){
		queue.add(new PVertex(start,0.0));
		for(Enumeration<String> e = graph.getVertices(); e.hasMoreElements();){
			String s = e.nextElement();
			if(!s.equals(start))queue.add(new PVertex(s,Integer.MAX_VALUE));
		}
	}
	
	public boolean step(){
		if(queue.size()==0)return true;
		PVertex a = queue.poll();
		System.out.println("Removing and adding to cloud > " + a);
		Hashtable<String, Double> edges = graph.getAdjacent(a.getName());
		cloud.add(a);
		for(PVertex p:queue){
			if(edges.containsKey(p.getName())){
				double ap = edges.get(p.getName());
				if(p.getDistance()>a.getDistance()+ap){
					p.setDistance(a.getDistance()+ap);
				}
			}
		}
		return step();
	}
	
	public class PVertex implements Comparable{
		
		private String name;
		private double distance;
		
		public PVertex(String name, double distance){
			this.name = name;
			this.distance = distance;
		}

		public double getDistance() {
			return distance;
		}

		public void setDistance(double distance) {
			this.distance = distance;
		}

		public String getName() {
			return name;
		}

		public void setName(String name) {
			this.name = name;
		}
		
		public int compareTo(Object arg0) {
			PVertex other = (PVertex)arg0;
			if(other.distance>this.distance)return -1;
			if(other.distance<this.distance)return 1;
			return 0;
		}
		
		@Override
		public boolean equals(Object obj) {
			PVertex other = (PVertex)obj;
			return other.name.equals(this.name);
		}
		
		@Override
		public String toString() {
			return "Vertex> " + name + ", Distance> " + distance;
		}
	}
	
	public static void main(String[] args) {
		Graph g = new Graph();
		g.initDijkstra();
		Dijkstra d = new Dijkstra(g);
		d.init();
		System.out.println(d.step());
		System.out.println();
	}
}
